import java.util.Arrays;

public class Solution4 {
    int lengthOfLIS(int[] nums) {
        // 定义数组：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        /*明确状态：dp[i]
        * 明确选择：nums[i]*/
        int[] dp = new int[nums.length];
        // 确定 base case：dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
        /*如何寻找状态转移方程？——归纳法
        * */
        for (int i = 0; i < nums.length; i++) {
            /*假设已经知道了 dp[0] ~ dp[i-1] 现在想求 dp[i] （ dp[i] 已经被初始化为 1 ）*/
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
